

#include<bits/stdc++.h>
using namespace std;

struct Node
{
    int val;
    Node* next;
    Node* random;
    Node(int x):val(x),next(nullptr),random(nullptr){};
    /* data */
};


class Solution
{
private:
    /* data */
public:
    Node* copyRandomList(Node* head){
        if(head==nullptr){
            return nullptr;
        }
        vector<Node*> vec;
        unordered_map<Node*,int> hash;
        Node* cur=head;
        int pos=0;
        while(cur!=nullptr){
            Node* temp=new Node(cur->val);
            vec.emplace_back(temp);
            hash[cur]=pos;
            ++pos;
            cur = cur->next;
        }

        for(int i=0;i<vec.size()-1;++i){
            vec[i]->next=vec[i+1];
        }
        pos=0;
        cur=head;
        while(cur!=nullptr){
            if(cur->random==nullptr){
                vec[pos]->random=nullptr;
            }
            else{
                int temp=hash[cur->random];
                vec[pos]->random=vec[temp];
            }
            ++pos;
            cur=cur->next;
        }
        return vec[0];
    }
};



int main(int argc, char const *argv[])
{
    /* code */
    return 0;
}
